#include <cstdlib>
#include <iostream>
#include <string.h>
#include <sstream>
#include "Algorithm.h"

using std::ofstream;
using namespace std;

/***************************************************************/
/*-------------------------------------------------------------*/
/*------------------ Greedy algorithm -------------------------*/
/*-------------------------------------------------------------*/
/***************************************************************/

static bool isNeighborsColored(NodeList * nl, int color) {
    bool colored = false;

    for (nodelist_it i = nl->begin(); i != nl->end(); ++i) {
        if ((*i) == nl->front())
            continue;
        if (color == (*i)->getColor()) {
            colored = true;
            break;
        }
    }
    return colored;
}

extern int greedy_algorithm(Graph * g) {
    Graph * g_tmp = g;
    vector<NodeList *> * adjacency_list = g_tmp->getAdjacencyList();

    int color_max = 0;
    bool colored;

    for (lnodelist_it i = adjacency_list->begin(); i != adjacency_list->end(); ++i) {
        Node * front_node = (*i)->front();

        colored = false;
        for (int c = 0; c <= color_max; c++) {
            if (!isNeighborsColored(*i, c)) {
                front_node->setColor(c);
                colored = true;
                break;
            }
        }
        if (!colored)
            front_node->setColor(++color_max);
    }

    return color_max + 1;
}


/***************************************************************/
/*-------------------------------------------------------------*/
/*------------------ Backtracking algorithm -------------------*/
/*-------------------------------------------------------------*/
/***************************************************************/


typedef list<Color>::iterator color_it;

static list<Color> * admissible_colors(NodeList * nl, int k) {
    //Initialisation
    list<Color> * adm_colors_list = new list<Color > ();
    for (int i = 0; i < k; i++)
        adm_colors_list->push_back(i);

    Color c;
    //On retire les couleurs déja utilisés :
    for (nodelist_it nl_it = nl->begin(); nl_it != nl->end(); nl_it++) {
        c = (*nl_it)->getColor();
        if (c != -1)
            adm_colors_list->remove(c);
    }

    return adm_colors_list;
}

static bool isColored(Graph *g) {
    vector<NodeList*> * al = g->getAdjacencyList();
    unsigned int i;
    for (i = 0; i < al->size(); i++) {
        NodeList * nl = (*al)[i];
        if (nl->front()->getColor() == -1)
            return false;
    }
    return true;
}

static int iteration = 0;

static string trace_id() {
    int i = ++iteration;
    ostringstream buffer;
    buffer << i;
    return "graph/trace_" + buffer.str() + ".dot";
}


static bool colored = false;
int current = 0;
int max_colorie = -1;

static int backtracking_aux(Graph * g, int k, unsigned int nl_index) {
    vector<NodeList *> *adjacency_list = g->getAdjacencyList();
    NodeList * nl = (*adjacency_list)[nl_index];
    Node * front_node = nl->front();

    list<Color> * adm_color = admissible_colors(nl, k);

    if (!adm_color->empty()) {
        int nl_index_next = nl_index + 1;
        for (color_it c_it = adm_color->begin(); c_it != adm_color->end(); c_it++) {
            front_node->setColor(*c_it);
            current++;
            //Trace
            //cout << "test" <<endl;
            //g->saveOnDotFile(trace_id().c_str());

            if (max_colorie < current)
                max_colorie = current;

            if (nl_index < adjacency_list->size() - 1)
                backtracking_aux(g, k, nl_index_next);

            //Optimisation (verification à la fin seulement)
            if ((adjacency_list->size() == nl_index + 1) && isColored(g))
                colored = true;

            //propagation ...
            if (colored)
                return true;
        }
        current--;
    } else {
        //Décoloration du noeud précédent
        NodeList * prev_nl = (*adjacency_list)[nl_index - 1];
        Node * prev_front_node = prev_nl->front();
        prev_front_node->setColor(-1);
        current--;
    }
}

extern int backtracking_algorithm(Graph * g, int k) {
    colored = false;
    max_colorie = -1;
    current = 0;
    backtracking_aux(g, k, 0);
    return max_colorie;
}


/***************************************************************/
/*-------------------------------------------------------------*/
/*------------------- No-choice algorithm ---------------------*/
/*-------------------------------------------------------------*/
/***************************************************************/


struct DNode {
    Node * node;
    NodeList * neighbors;
    int degree;
};

static DNode * getGreaterDegreeNode(list<DNode *> * vertices) {
    int max = -1;
    DNode * n = NULL;
    for (list<DNode *>::iterator i = vertices->begin(); i != vertices->end(); ++i) {
        int degree = (*i)->degree;
        if (max < degree) {
            max = degree;
            n = (*i);
        }
    }
    return n;
}

static list<DNode *> * intersection(list<DNode *> * vertices, NodeList * neighbors) {
    list<DNode *> * inter = new list<DNode *>();
    for (list<DNode *>::iterator i = vertices->begin(); i != vertices->end(); i++) {
        for (nodelist_it j = neighbors->begin(); j != neighbors->end(); j++) {
            if ((*i)->node == (*j))
                inter->push_back((*i));
        }
    }

    delete vertices;
    return inter;
}

static int greaterClique(Graph * graph) {
    Graph * g = graph->clone();

    NodeList * clique = new NodeList();
    list<DNode *> * vertices = new list<DNode *>();

    vector<NodeList *> *adj_list = g->getAdjacencyList();

    //Calcul des degrés de chaque sommets
    for (lnodelist_it i = adj_list->begin(); i != adj_list->end(); ++i) {
        DNode * dnode = (DNode *) malloc(sizeof (*dnode));
        dnode->degree = (*i)->size() - 1;
        dnode->node = (*i)->front();
        NodeList * neighbors = *i;
        neighbors->remove(neighbors->front());
        dnode->neighbors = neighbors;
        vertices->push_back(dnode);
    }

    //Recherche du sommet de plus grand degré
    while (vertices->size() != 0) {
        DNode * dnode = getGreaterDegreeNode(vertices);
        Node * nmax = dnode->node;
        clique->push_back(nmax);
        NodeList * neighbors = dnode->neighbors;
        vertices = intersection(vertices, neighbors);
    }

    int c = 0;
    //Coloration de la plus grande clique
    for (nodelist_it i = clique->begin(); i != clique->end(); ++i) {
        int index = (*i)->getValue();
        vector<NodeList *> * adj = graph->getAdjacencyList();
        NodeList * nl = (*adj)[index];
        Node * n = nl->front();

        n->setColor(c++); // ;-)
    }
    return clique->size();
}


extern int nochoice_algorithm(Graph * g, int k) {
    int size = greaterClique(g);
    if (g->getAdjacencyList()->size() == k && size == k)
        return k;

    if (size > k)
        return 0;

    current = size;

    vector<NodeList *> * adj_l = g->getAdjacencyList();
    vector<NodeList *> * not_coloried_nl = new vector<NodeList *>();

    //Recherche des sommets non coloriés
    for (lnodelist_it i = adj_l->begin(); i != adj_l->end(); ++i) {
        NodeList * nl = (*i);
        Node * front_node = nl->front();
        if (front_node->getColor() == -1)
            not_coloried_nl->push_back(nl);
    }
    vector<NodeList *> * not_coloried_nl_next = new vector<NodeList *>();

    //Coloration des sommets avec une couleur admissible
    bool done = true;
    while (done) {
        done = false;
        for (lnodelist_it i = not_coloried_nl->begin(); i != not_coloried_nl->end(); ++i) {
            NodeList * nl = (*i);
            Node * front_node = nl->front();
            if (front_node->getColor() == -1) {
                list<Color> * adm_color = admissible_colors(nl, k);
                if (adm_color->size() == 1) {
                    Color c = adm_color->front();
                    front_node->setColor(c);
                    current++;
                    done = true;
                } else {
                    not_coloried_nl_next->push_back(nl);
                }
            }
        }
        //A chaque fin de boucle on met à jour les sommets non coloriés
        delete not_coloried_nl;
        not_coloried_nl = not_coloried_nl_next;
        not_coloried_nl_next = new vector<NodeList *>();
    }
    return current;
}

//version identique que la précédente avec une coloration gloutonne
//sur les sommets non coloriés (plus d'une couleur admissible)
extern int nochoice_algorithm_optimized(Graph * g, int k) {

    int size = greaterClique(g);
    if (g->getAdjacencyList()->size() == k && size == k)
        return k;
    
    if (size > k)
        return 0;

    current = size;


    vector<NodeList *> * adj_l = g->getAdjacencyList();
    vector<NodeList *> * not_coloried_nl = new vector<NodeList *>();

    for (lnodelist_it i = adj_l->begin(); i != adj_l->end(); ++i) {
        NodeList * nl = (*i);
        Node * front_node = nl->front();
        if (front_node->getColor() == -1)
            not_coloried_nl->push_back(nl);
    }

    vector<NodeList *> * not_coloried_nl_next = new vector<NodeList *>();

    bool done = true;
    while (done) {
        done = false;
        for (lnodelist_it i = not_coloried_nl->begin(); i != not_coloried_nl->end(); ++i) {
            NodeList * nl = (*i);
            Node * front_node = nl->front();
            if (front_node->getColor() == -1) {
                list<Color> * adm_color = admissible_colors(nl, k);
                if (adm_color->size() == 1) {
                    Color c = adm_color->front();
                    front_node->setColor(c);
                    current++;
                    done = true;

                } else {
                    not_coloried_nl_next->push_back(nl);
                }
            }
        }

        delete not_coloried_nl;
        not_coloried_nl = not_coloried_nl_next;
        not_coloried_nl_next = new vector<NodeList *>();
    }

    int nb_colored = 0;
    for (lnodelist_it i = not_coloried_nl->begin(); i != not_coloried_nl->end(); ++i) {
        nb_colored++;
        list<Color> * adm_color = admissible_colors(*i, k);

        if (!adm_color->empty()) {
            (*i)->front()->setColor(adm_color->front());
            current++;
            nb_colored--;
        } else
            break;
    }

    return current;
}


/***************************************************************/
/*-------------------------------------------------------------*/
/*------------------ Sat-reduction ----------------------------*/
/*-------------------------------------------------------------*/
/***************************************************************/


static vector<string> explode(const string &delimiter, const string &str) {
    vector<string> arr;

    int strleng = str.length();
    int delleng = delimiter.length();
    if (delleng == 0)
        return arr;

    int i = 0;
    int k = 0;
    while (i < strleng) {
        int j = 0;
        while (i + j < strleng && j < delleng && str[i + j] == delimiter[j])
            j++;

        if (j == delleng) {
            arr.push_back(str.substr(k, i - k));
            i += delleng;
            k = i;
        } else
            i++;

    }
    arr.push_back(str.substr(k, i - k));
    return arr;
}

extern void sat_colouring(Graph * g, int k, string sat_result_file_path) {
    ifstream sat_result_file(sat_result_file_path.c_str());
    string result;

    vector<NodeList *> * adj_l = g->getAdjacencyList();

    getline(sat_result_file, result);
    if (result.compare("SAT\n")) {
        getline(sat_result_file, result);
        vector<string> t = explode(" ", result);
        int t_size = t.size();
        for (int i = 0; i < t_size - 1; i++) {
            int valeur = atoi(t[i].c_str());
            if (valeur > 0) {
                int color = valeur % k;
                int node_index;
                if (valeur <= k)
                    node_index = 0;
                else if ((valeur % k) == 0)
                    node_index = valeur / k - 1;
                else
                    node_index = valeur / k;
                ((*adj_l)[node_index])->front()->setColor(color);
            }
        }
    }
}
